package com.leetcode.dynamic_programming.zero_one_backpack;

/**
 * @author Dennis Li
 * @date 2020/7/20 20:18
 */
public class CoinChange2_518 {

    public int change(int amount, int[] coins) {
        final int[] dp = new int[amount + 1];
        dp[0] = 1;
        // 状态压缩
        // 先根据硬币，来试每一种状态
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

    int change2(int amount, int[] coins) {
        int n = coins.length;
        // 选择多少个硬币来凑
        // 第二个状态是凑够了多少钱
        int[][] dp = new int[n + 1][amount + 1];
        // base case
        for (int i = 0; i <= n; i++)
            dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++)
                // 两种路径
                if (j - coins[i - 1] >= 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                else
                    dp[i][j] = dp[i - 1][j];
        }
        return dp[n][amount];
    }

    static class Solution {
        public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int coin : coins) {
                for (int i = coin; i <= amount; i++) {
                    dp[i] += dp[i - coin];
                }
            }
            return dp[amount];
        }
    }
}
